package a03_哈希;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * a08_四数之和
 * </p>
 *
 * @author flyduck
 * @since 2024-06-27
 */
public class a09_四数之和复习1 {


    public static void main(String[] args) {
//        int[] nums = {-3,-2,-1,0,0,1,2,3};
//        int[] nums = {1000000000,1000000000,1000000000,1000000000};
        int[] nums = {2,2,2,2,2};
        List<List<Integer>> lists = fourSum(nums, 8 );
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> resultList = new ArrayList<>();
        outer1:for (int i = 0; i < nums.length; i++) {
            if(nums[i] > 0 && target > 0 && nums[i] > target){
               continue outer1;
            }
            if(i > 0 && nums[i] == nums[i - 1]){
                continue outer1;
            }
            outer2:for (int j = i + 1; j < nums.length; j++) {
                if(nums[i] + nums[j] > 0 && target > 0 && nums[i] + nums[j] > target){
                    continue outer2;
                }
                if(j > i + 1 && nums[j] == nums[j - 1]){
                    continue outer2;
                }
                int leftIndex = j + 1;
                int rightIndex = nums.length - 1;
                inner:while (leftIndex < rightIndex){
                    if(leftIndex > j + 1 && nums[leftIndex] == nums[leftIndex-1]){
                        leftIndex++;
                        continue inner;
                    }
                    if(rightIndex < nums.length - 1 && nums[rightIndex] == nums[rightIndex+1]){
                        rightIndex--;
                        continue inner;
                    }
                    long sum = (long)nums[i] + nums[j] + nums[leftIndex] + nums[rightIndex];
                    if (sum > target) {
                        rightIndex--;
                        continue inner;
                    }else if(sum < target){
                        leftIndex++;
                        continue inner;
                    }else {
                        List<Integer> result = new ArrayList<>();
                        result.add(nums[i]);
                        result.add(nums[j]);
                        result.add(nums[leftIndex]);
                        result.add(nums[rightIndex]);
                        resultList.add(result);
                        leftIndex++;
                        rightIndex--;
                        continue inner;
                    }
                }
            }
        }
        return resultList;
    }
}
